#include <unordered_map>
#include <vector>
#include <iostream>

using namespace std;

struct ListNode {
	int val;
	ListNode *next;
	ListNode() : val(0), next(nullptr) {}
	ListNode(int x) : val(x), next(nullptr) {}
	ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
		// 1.暴力算法 但是对于特别大的数字无法起作用
		// long long newNum1 = listToNum(l1);
		// cout << "newNum1:" << newNum1 << endl;
		// long long newNum2 = listToNum(l2);
		// cout << "newNum2:" << newNum2 << endl;
		// long long num = newNum1 + newNum2;
		// return numToList(num);
		
		// 双指针同步进行
		int flag = 0; // 进1标志
		int i = 0; // 计数
		
		ListNode * pos;
		ListNode * start;
		
		int leftNode = 0; // 默认是两个链表长度一致 0-一致 1-l1短 2-l2短
		while(1){
			if(!l1 || !l2){
				if(!l1 && l2){
					leftNode = 1;
				}
				if(l1 && !l2){
					leftNode = 2;
				}
				break;
			}
			
			ListNode * newListNode = new ListNode;
			newListNode->next = NULL;
			
			int val = l1->val + l2->val;
			
			if(flag == 1){
				val++;
			}
			if(val >= 10){
				flag = 1;
				newListNode->val = val - 10;
			} else {
				flag = 0;
				newListNode->val = val;
			}
			
			if(i == 0) {
				start = newListNode;
				pos = newListNode;
				i++;
			} else {
				pos->next = newListNode;
				pos = pos->next;
			}
			
			l1 = l1->next;
			l2 = l2->next;
		}
		
		ListNode * second;
		if(leftNode == 1){
			second = l2;
		}else{
			second = l1;
		}

		if(second){
			while(second){
				ListNode * newListNode = new ListNode;
				newListNode->next = NULL;
				int val;
				if(flag == 1){
					val = second->val + 1;
				}else{
					val = second->val;
				}
				if(val >= 10){
					val = val - 10;
					flag = 1;
				}else{
					flag = 0;
				}
				newListNode->val = val;
				pos->next = newListNode;
				pos = pos->next;
				second = second->next;
			}
		}
		if(flag == 1){
			ListNode * newListNode = new ListNode;
			newListNode->next = NULL;
			newListNode->val = 1;
			pos->next = newListNode;
			pos = pos->next;
		}
		
		return start;
    }
	
	ListNode* addTwoNumbers2(ListNode* l1, ListNode* l2) {
		int flag = 0;
		ListNode * pos;
		ListNode * head;
		int i = 0;
		while(1){
			if(!l1 && !l2){
				break;
			}
			int val = 0;
			if(l1){
				val += l1->val;
                l1 = l1->next;
			}
			if(l2){
				val += l2->val;
                l2 = l2->next;
			}
			if(flag == 1){
				val++;
			}
			ListNode * newListNode = new ListNode;
			newListNode->next = NULL;
			if(val >= 10){
				newListNode->val = val- 10;
				flag = 1;
			}else{
				newListNode->val = val;
				flag = 0;
			}
			if(i == 0){
				head = newListNode;
				pos = head;
				i++;
			}else{
				pos->next = newListNode;
				pos = pos->next;
			}
			
		}
		if(flag == 1){
			ListNode * newListNode = new ListNode;
			newListNode->next = NULL;
			newListNode->val = 1;
			pos->next = newListNode;
			pos = pos->next;
		}
		return head;
	}
	
	
	
	
	long long listToNum(ListNode * listNode){
		long long num = 0;
		// 3 4 2 入到链表中的顺序为 2 -> 4 -> 3
		int i = 0;
		while(listNode){
			num = num + listNode->val * pow(10, i);
			listNode = listNode->next;
			i++;
		}
		return num;
	}
	
	ListNode * numToList(long long num){
		ListNode * head = new ListNode(num % 10);
		head->next = NULL;
		num = num / 10;
		
		ListNode * cur = head;
		while(num > 0){
			ListNode * tmp = new ListNode(num % 10);
			tmp->next = NULL;
			
			cur->next = tmp;
			cur = tmp;
			num = num/10;
		}
		return head;
	}
	
	void showListNode(ListNode* l){
		while(l){
			cout << l->val << " ";
			l = l->next;
		}
		cout << endl;
	}
	
	long long pow(int x, int y){
		long long num = 1;
		for(int i = 0; i < y; i++){
			num = x * num;
		}
		return num;
	}
};

int main(){
	
	long long num1 = 243;
	int num2 = 564;
	Solution so;
	// int pow = so.pow(-10, 2);
	// cout << pow << endl;
	// return 0;
	ListNode * l1 = so.numToList(num1);
	ListNode * l2 = so.numToList(num2);
	// so.showListNode(l1);
	// so.showListNode(l2);
	ListNode * l3 = so.addTwoNumbers(l1, l2);
	so.showListNode(l3);
	// cout << "num1: ";
	// so.showListNode(l1);
	// cout << endl;
	// cout << "num2: ";
	// so.showListNode(l2);
	
	// int newNum1 = so.listToNum(l1);
	// int newNum2 = so.listToNum(l2);
	// cout << "n1:" << newNum1 << ",n2:" << newNum2 << endl;
	
	// int newNum = so.listToNum(l1);
	// cout << newNum << endl;
}